package com.LeetCode.List;

import org.junit.Test;

public class isPalindrome {

    /**
     * 判断回文链表
     */
    public boolean isPalindrome(ListNode head) {
        if(head == null)
            return true;

        ListNode firstHalfHead = getEndOfFirstHalf(head);
        ListNode secondHalfStart = reverseList(firstHalfHead);

        ListNode p1 = head;
        ListNode p2 = secondHalfStart;
        boolean res = true;

        while(p1 != null && p2 != null){
            if(p1.val != p2.val)
                return false;
            p1 = p1.next;
            p2 = p2.next;
        }
        return true;
    }

    public ListNode reverseList(ListNode head){
        ListNode prev = null;
        ListNode pNode = head;
        while(pNode != null){
            ListNode next = pNode.next;
            pNode.next = prev;
            prev = pNode;
            pNode = next;
        }
        return prev;
    }

    public ListNode getEndOfFirstHalf(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    @Test
    public void test(){

    }
}
